from math import fabs, log
from random import uniform
import logging
from mca import Recurrencer, ParamsSeeker
from set_cover import approx

class SetCoverRecurrencer(Recurrencer):
    def __compute_in_deltas(self):
        self.__in_deltas = \
            (0,

             self.__alphas[0] + self.__betas[0],

             min(2 * self.__alphas[0], 
                 self.__alphas[1]) + 
             self.__betas[0],

             min(3 * self.__alphas[0], 
                 self.__alphas[0] + self.__alphas[1]) + 
             self.__betas[0],

             min(3 * self.__alphas[0], 
                 self.__alphas[0] + self.__alphas[1], 
                 self.__alphas[2]) + 
             self.__betas[0])

    def __compute_dlt_betas(self):
        deltalized = [self.__betas[0]]
        for i in range(len(self.__betas) - 1):
            deltalized.append(self.__betas[i + 1] - self.__betas[i])
        deltalized.append(1.0 - self.__betas[-1])

        self.__dlt_betas = tuple(deltalized)

    # params should cover elements from 2nd, for xmpl. alpha(2), beta(2)
    # even if those are equal 0. elements not covered are assumed to be 
    # equal 1.
    def __init__(self, params, min_set_size = 3):
        assert(len(params['alpha']) >= 3 and len(params['beta']) >= 1)
        assert(min_set_size >= 3)

        self.__alphas = tuple(params['alpha'])
        self.__betas = tuple(params['beta'])

        self.__min_set_size = min_set_size

        self.__num_alphas = len(self.__alphas)
        self.__num_betas = len(self.__betas)

        self.__compute_dlt_betas()
        self.__compute_in_deltas()

        # it's more efficient to have all frequencies calculated separately
        self.__frequencies = {}

        # delta_alpha == 0 and delta_beta == 0 for |S| >= max_set_size
        self.__max_set_size = max(max(self.__num_alphas, self.__num_betas) + 3,
                                  self.__min_set_size)

        # first bucket is for elements with frequency 1, which we acturally
        # don't count. last bucket is for elements with high frequencies that
        # betas don't cover, for which we assume beta is 1
        sieve = self.add_elements(self.__max_set_size, self.__num_betas + 1)

        for i in reversed(range(self.__min_set_size, self.__max_set_size + 1)):
            sieve = [f for f in sieve if sum(f[:-1]) <= i]
            tmp = []
            for l in sieve:
                l = list(l)
                l[-1] = i - sum(l[:-1])
                tmp.append(tuple(l))
            assert(len(tmp) > i)
            self.__frequencies[i] = tuple(tmp)
        

    def reset(self, params):
        assert(len(params['alpha']) == self.__num_alphas and 
               len(params['beta']) == self.__num_betas)

        self.__alphas = tuple(params['alpha'])
        self.__betas = tuple(params['beta'])
        self.__compute_dlt_betas()
        self.__compute_in_deltas()

    def __alpha_s(self, set_size):
        self.__alpha = 0
        if set_size - 1 > self.__num_alphas:
            self.__alpha = 1
        elif set_size > 1:
            self.__alpha = self.__alphas[set_size - 2]
        return self.__alpha

    def __min_dlt_alpha_s(self, set_size):
        l = [self.__alpha_s(i + 1) - self.__alpha_s(i) for i in range(1, set_size)]
        return min(l)

    def __rec_out(self, set_size):
        ret = []

        for frequency in self.__frequencies[set_size]:
            assert(len(frequency) == len(self.__dlt_betas))
            # for frequencies > self.__dlt_betas, delta beta == 0
            fxdb = [f * b for (f, b) in zip(frequency, self.__dlt_betas)]

            if frequency[0] < 3:
                delta = self.__in_deltas[frequency[0]]
            elif frequency[0] == 3 and set_size == 3:
                delta = self.__in_deltas[3]
            elif frequency[0] >= 3 and set_size >= 4:
                delta = self.__in_deltas[4]
            else:
                logging.debug('freq[0]: %d, set_size: %d' % (frequency[0], set_size))
                assert(False)

            ret.append(self.__alpha_s(set_size) + sum(fxdb) + delta)
            
        return ret

    def __rec_in(self, set_size):
        ret = []

        for frequency in self.__frequencies[set_size]:
            assert(len(frequency) == self.__num_betas + 1)
            # for frequencies > self.__dlt_betas, delta beta == 0
            fxb = [f * b for (f, b) in zip(frequency, self.__betas)]

            w = [(i + 1) * frequency[i] for i in range(len(frequency))]

            ret.append(self.__alpha_s(set_size) +
                       sum(fxb) +
                       frequency[-1] +
                       self.__min_dlt_alpha_s(set_size) * sum(w))


        return ret

    def __rec(self, set_size):
        r1 = self.__rec_out(set_size)
        r2 = self.__rec_in(set_size)

        assert(len(r1) == len(r2))

        return zip(r1, r2)

    def get_max_root(self):
        ret = 1.0

        for set_size in range(self.__min_set_size, self.__max_set_size + 1):
            r = [self.get_root(d1, d2) for (d1, d2) in self.__rec(set_size)]
            assert(len(r) > 0)
            r.append(ret)
            ret = max(r)

        return ret

# ---------- D E B U G -----------
assert_r = SetCoverRecurrencer({'alpha': (0.377, 0.754, 0.909, 0.976), 
                        'beta':  (0.399, 0.767, 0.929, 0.985)}, 3)

assert(int(log(assert_r.get_max_root(), 2) * 1000) == 305)
# --------------------------------

# r = SetCoverRecurrencer({'alpha': (0.004, 0.619, 0.842, 0.951), 
#                  'beta':  (0.553, 0.831, 0.945, 0.993)})

# print r.get_max_root()

# r = SetCoverRecurrencer({'alpha': (0.002, 0.640, 0.849, 0.950, 1.000), 
#                  'beta':  (0.463, 0.768, 0.925, 0.999, 1.000)})


# print r.get_max_root()


# ----------------------------------------------------

class SetCoverParamsSeeker(ParamsSeeker):
    @classmethod
    def seek_best_params(cls, min_set_size, max_set_size):
        iterations = 200
        min_range = 0.00001

        range_var = 1.0
        ones = tuple([1 for _ in range(max_set_size - 3)])
        ret = {'alpha': ones, 'beta': ones}
        r = SetCoverRecurrencer(ret, min_set_size)
        ret_root = r.get_max_root()

        while (range_var > min_range):
            # print 'yield'
            for _ in range(iterations):
                tmp = {'alpha': cls.rand_params(ret['alpha'], range_var), 
                       'beta': cls.rand_params(ret['beta'], range_var)}
                r.reset(tmp)
                tmp_root = r.get_max_root()
                if tmp_root < ret_root:
                    ret = tmp
                    ret_root = tmp_root
                    d = min_set_size - 1
                    a = approx(d)
                    print '  %d & %f & %f & %f & %f\\\\' % (d, a, ret_root, log(ret_root, 2), a * log(ret_root, 2))
                    # print ret_root
                    print ret
                    # print range_var
            range_var /= 2

        print ret_root
        return ret

hdlr = logging.FileHandler('log')
logging.getLogger().addHandler(hdlr)
# logging.basicConfig(file = 'log')
logging.getLogger().setLevel(logging.INFO)

max_set_size = 12

for i in range(7, max_set_size):
    logging.critical('fda')
    print '####### current set size: %d #######' % i
    print SetCoverParamsSeeker.seek_best_params(3, i)

    
# from cProfile import run
# run('print seek_best_params(7)')
